Packet forwarding devices, such as layer 3 or Internet protocol (IP) routers, typically use one or more tables to store packet forwarding information. Typically, packet forwarding devices include one or more hardware-implemented tables in addition to software-implemented tables in order to reduce packet forwarding information lookup time. For example, layer 3 packet forwarding devices may include a hardware-implemented host table populated with entries corresponding to individual hosts. When a packet arrives at a layer 3 packet forwarding device, a lookup may first be performed in the hardware host table. If the lookup is successful, the packet may be forwarded to a host corresponding to the matching entry in the table. If the lookup in the hardware host table fails to locate a match, a lookup may be performed in a longest prefix matching (LPM) table to locate the entry with the longest prefix that matches the address in the received packet. If the lookup in the LPM table fails to locate a longest prefix match, a software routing table may be searched in order to successfully forward the packet.
In some implementations, a hardware-implemented host table stores entries corresponding to hosts directly connected to the packet forwarding device. Each entry in the host table may include an IP address of a locally connected host and corresponding forwarding information. When a layer 3 packet arrives at the packet forwarding device, a lookup may be performed in the host table based on the destination IP address in the packet. This lookup is typically performed using a hashing function that identifies matching entries using a search key. If a matching entry is located, the corresponding packet forwarding information is extracted from the host table and used to forward the packet to the destination host. Host tables are typically searched before other tables because they store the most specific forwarding information for layer 3 packets.
A hardware-implemented LPM table stores subnet addresses and subnet masks to be applied to destination IP addresses of incoming packets. When a layer 3 packet is received, logical steps may be performed by a packet forwarding device where the subnet mask for each entry in the LPM table is applied to the destination IP address of the packet, and the masked address is searched in the table. In some implementations, these steps may be performed in a single LPM lookup using a special data structure, such as a Radix tree. The entry with the longest prefix that matches the masked address in the received packet is used to extract next hop address information for the packet. The next hop address typically corresponds to the next hop or machine in a path through which a remote host corresponding to the destination IP address in the packet is reachable. Using an LPM table allows remote hosts to be identified by next hops without requiring entries in the LPM table for each individual remote host. Thus, LPM tables may reduce a large number of hosts into fewer route entries by combining entries with the same next hop information. This allows an LPM table to store matching entries for more hosts than a host table of the same size.
Software lookups are performed by searching a much larger software table that stores layer 3 packet forwarding information. Lookups performed in software are significantly slower than lookups performed in hardware and therefore, it is desirable to perform as few lookups in software as possible.
As stated above, both host and LPM tables may be implemented or stored in hardware of a layer 3 packet forwarding device. In some implementations, the memory space available for both tables is shared. In order to increase the routing efficiency of conventional layer 3 packet forwarding devices, the relative sizes of the host and LPM tables are based on the expected number of communicating IP hosts. For example, edge devices that connect to a small number of hosts may utilize more memory for the host table and less for the LPM table. Devices, referred to as aggregators, that serve many communicating IP hosts may utilize more memory for the LPM table and less for the host table. Aggregators typically connect numerous smaller devices to a network infrastructure backbone or core network device and therefore route packets for a large number of hosts.
In edge devices, it may be desirable to route packets primarily using a host table, since the size of the host table would be small. In aggregators, it may be desirable to route packets primarily using an LPM table, since its entries represent plural hosts and populating a host table with all possible hosts would result in a table size that exceeds available memory space.
Layer 3 packet forwarding devices may have multiple modules, each containing host and LPM tables, for forwarding layer 3 packets. Conventionally, these modules are programmed identically and contain identical host and LPM tables as described above. However, as described above, it may be desirable to route some packets primarily using a host table and others primarily using an LPM table. Conventional IP packet forwarding devices do not provide for such varied operation.
Accordingly, there exists a need for improved methods, systems, and computer program products for routing layer 3 packets.